package com.zh.note.huawei.twohundred.人气最高的店铺;

import java.util.*;

/**
 * 递归
 */
public class Main {
    //存储每个店铺被投票的次数
    public static Map<Integer, Integer> popularityMap = new HashMap<>();
    public static int minMoney = Integer.MAX_VALUE;
    public static int money;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        String[] input1 = scanner.nextLine().split(",");
        int shopCount = Integer.parseInt(input1[0]);
        int voteCount = Integer.parseInt(input1[1]);
        // 输入的数据
        List<int[]> peopleList = new ArrayList<>();
        popularityMap.put(1, 0);

        for (int i = 0; i < shopCount; i++) {
            String[] input2 = scanner.nextLine().split(",");
            int shop = Integer.parseInt(input2[0]);
            int popularity = Integer.parseInt(input2[1]);
            if (shop != 1) {
                peopleList.add(new int[]{shop, popularity});
            }
            popularityMap.put(shop, popularityMap.getOrDefault(shop, 0) + 1);
        }

        dfs(peopleList, new ArrayList<>(), 0);

        System.out.println(minMoney);
    }

    // 处理投票
    public static void dfs(List<int[]> peopleList, List<int[]> selectedList, int index) {
        if (isMax(selectedList) && minMoney > money) {
            minMoney = money;
            return;
        }//剪枝
        if (money > minMoney) {
            return;
        }
        for (int i = index; i < peopleList.size(); i++) {
            selectedList.add(peopleList.get(i));
            dfs(peopleList, selectedList, i + 1);
            selectedList.remove(selectedList.size() - 1);
        }

    }

    // 改变changeList后判断店铺1否达到最大值
    public static boolean isMax(List<int[]> selectedList) {
        Map<Integer, Integer> tempMap = new HashMap<>(popularityMap);
        money = 0;
        for (int[] ints : selectedList) {
            int shop = ints[0];
            money += ints[1];
            tempMap.put(shop, tempMap.get(shop) - 1);
            tempMap.put(1, tempMap.get(1) + 1);
        }

        List<Map.Entry<Integer, Integer>> entryList = new ArrayList<>(tempMap.entrySet());
        entryList.sort((a, b) -> b.getValue() - a.getValue());

        int firstShop = entryList.get(0).getKey();
        //第一个是1，并且1出现的次数大于第二个
        if (firstShop == 1 && (entryList.size() == 1 || entryList.get(0).getValue() > entryList.get(1).getValue())) {
            return true;
        }

        return false;
    }
}

